⟸ Go Back ⟸

Exercise 15 (Homework 2).

(regular languages, first half, hard exercise)

First half of regular is regular

Given a language L, we define \mathtt{FirstHalf}(L) as the set of strings that constitute the first half of strings of even length in L, that is, \mathtt{FirstHalf}(L)= \{x \mid \exists y \, (|x|=|y| \, \wedge \, xy \in L)\}. Show that if L is regular, then \mathtt{FirstHalf}(L) is regular.